package acm.蓝桥杯15;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class J {
    static long[] bucket = new long[2];   //0小桶，1大桶
    static List<Integer> girls;
    static List<Integer> boys;
    static Map<Integer, Integer> map;
    static int N;

    public static void main(String[] args) {
        Reader sc = new Reader();
        int n = sc.nextInt();
        while (n-- > 0) {
            N = sc.nextInt();
            String line = sc.nextLine();
            girls = new ArrayList<>();
            boys = new ArrayList<>();
            map = new HashMap<>();
            bucket[0] = 0;
            bucket[1] = 0;
            for (int i = 0; i < N; i++) {
                int k = i + 1;
                if (line.charAt(i) == '0') {
                    girls.add(k);
                    bucket[0] += k;
                    map.put(k, 2);
                } else {
                    boys.add(k);
                    bucket[1] += k;
                    map.put(k, 3);
                }
            }
            List<Integer> lessList = girls;
            List<Integer> moreList = boys;
            if (bucket[0] > bucket[1]) {  //如果小桶重
                swap();
                lessList = boys;
                moreList = girls;
            }
            if (fun(lessList, moreList, moreList.size() - 1)) {
                handlePrint();
            }else {
                System.out.println("-1");
            }
        }
    }

    private static void handlePrint() {
        for (int i = 1; i <= N; i++) {
            System.out.print(map.get(i));
        }
        System.out.println();
    }

    /**
     * 返回是否可以把大桶小桶重量放平衡
     *
     * @param lessList
     * @param moreList
     * @param moreIndex
     * @return
     */
    public static boolean fun(List<Integer> lessList, List<Integer> moreList, int moreIndex) {
        if (bucket[0] == bucket[1]) {  //如果两个桶重量相等
            return true;
        }
        if (moreIndex < 0) {
            return false;
        }
        int more = moreList.get(moreIndex);
        bucket[0] += more;
        bucket[1] -= more;
        if (fun(lessList, moreList, moreIndex - 1)) {   //移走more可以平衡
            swapGroup(more);
            return true;
        }
        bucket[0] -= more;  //不移走more，移走后面的
        bucket[1] += more;
        //不移走more，移走后面的
        return fun(lessList, moreList, moreIndex - 1);
    }

    public static void swapGroup(int i) {
        int v = map.get(i);
        switch (v) {
            case 2:
                map.put(i, 1);
                break;
            case 3:
                map.put(i, 4);
                break;
            case 1:
                map.put(i, 2);
                break;
            case 4:
                map.put(i, 3);
                break;
        }
    }

    public static void swap() {
        long temp = bucket[0];
        bucket[0] = bucket[1];
        bucket[1] = temp;
    }

    static
    class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }
        public void clear(){
            tokenizer = new StringTokenizer("");
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble(){
            return Double.parseDouble(next());
        }
//    public BigInteger nextBigInt() {
//        return new BigInteger(next());
//    }
    }

}
